<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    class Dictionay {
      constructor () {
        this.items = {}
      }
      // 判断字典中是否含有key
      has (key) {
        return this.items.hasOwnProperty(key)
      }
      //在字典中添加键值对
      set (key, value) {
        this.items[key] = value
      }
      // 删除指定的key
      remove (key) {
        if (!this.has(key)) return false
        delete this.items[key]
      }
      // 获取指定的key
      get (key) {
        return this.has(key) ? this.items[key] : undefined
      }
      // 获取所有的value
      keys () {
        return Object.values(this.items)
      }
      // 获取字典中键值对的个数
      size () {
        return this.keys().length
      }
      // 清空
      clear () {
        this.items = {}
      }
    }
    // 封装图类
    class Graph {
      constructor () {
        this.vertexes = []
        this.adjList = new Dictionay() // 存储边信息
      }
      // 添加顶点
      addVertex (val) {
        // 添加点
        this.vertexes.push(val)
        // 添加点的关系, 采用邻接矩阵法 结构用字典
        this.adjList.set(val, [])
      }
      // 添加边
      addEdge (val1, val2) {
        //边是两个顶点的边
        this.adjList.get(val1).push(val2)
        this.adjList.get(val2).push(val1)
      }
      // 输出图结构
      toString () {
        let res = ''
        for (let i = 0; i < this.vertexes.length; i++) {
          res += this.vertexes[i] + "->"
          let adj = this.adjList.get(this.vertexes[i])
          for (let j = 0; j < adj.length; j++) {
            res += adj[j] + ""
          }
          res += "\n"
        }
        return res
      }
      // 初始化顶点的颜色
      _initializeColor () {
        // 白色:表示该顶点还没有被访问
        // 灰色: 表示该顶点被访问过 但并未被探索过
        // 黑色: 表示该顶点被访问过且被完全探索过
        let colors = []
        for (let i = 0; i < this.vertexes.length; i++) {
          colors[this.vertexes[i]] = 'white'
        }
        return colors
      }
      // 遍历图:完全探索一个顶点要求我们便查看该顶点的每一条边
      // BFS: 从指定的第一个顶点遍历图,先访问其所有的相邻点 就像访问图的一层
      bfs (handle) {
        // 广度优先搜索
        // 1.初始化所有颜色
        let color = this._initializeColor()
        // 2. 创建一个队列
        let queue = []
        // 3.将传入的顶点放入队列
        queue.push(this.vertexes[0])
        // 4.依赖队列操作数据 队列不为空时一直持续
        while (queue.length > 0) {
          // 4.1 拿到队头
          let qVal = queue.shift() // 队头即数组第一个元素
          // 4.2 拿到队头所关联的点并设置为访问中状态
          let qAdj = this.adjList.get(qVal)
          color[qVal] = 'gray'
          // 4.3 将队头所关联的点添加到队尾
          for (let i = 0; i < qAdj.length; i++) {
            let a = qAdj[i]
            if (color[a] === 'white') {
              color[a] = 'gray'
              queue.push(a)
            }
          }
          // 4.4 设置访问完的点为黑色
          color[qVal] = 'black'
          if (handle) {
            handle(qVal)
          }
        }
      }
      // 深度优先 递归的本质就是函数栈的调用
      dfs (handle) {
        // 1. 初始化颜色
        let color = this._initializeColor()
        // 2. 遍历所有顶点 开始访问 
        for (let i = 0; i < this.vertexes.length; i++) {
          if (color[this.vertexes[i]] === 'white') {
            this._dfsVisit(this.vertexes[i], color, handle)
          }
        }
      }
      _dfsVisit (val, color, handle) {
        // 1. 将颜色设置为访问中
        color[val] = 'gray'
        // 2. 执行相应的回调
        if (handle) {
          handle(val)
        }
        // 3. 拿与该点相邻的点 对每个点操作
        let adj = this.adjList.get(val)
        for (let i = 0; i < adj.length; i++) {
          let w = adj[i]
          // 如果相邻点为未访问状态,则开始访问
          if (color[w] === 'white') {
            this._dfsVisit(w, color, handle)
          }
        }
        //4. 处理完后设置未访问过该节点
        color[val] = 'black'
      }
    }
    let graph = new Graph()
    let myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
    for (let i = 0; i < myVertexes.length; i++) {
      graph.addVertex(myVertexes[i])
    }
    // 添加边
    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('A', 'D');
    graph.addEdge('C', 'D');
    graph.addEdge('C', 'G');
    graph.addEdge('D', 'G');
    graph.addEdge('D', 'H');
    graph.addEdge('B', 'E');
    graph.addEdge('B', 'F');
    graph.addEdge('E', 'I');
    console.log(graph);
    console.log(graph.toString());
    // 调用广度优先算法
    let result = ""
    graph.bfs(function (v) {
      result += v + " "
    })
    console.log(result);
    let rst = ''
    graph.dfs(function (v) {
      rst += v + ' '
    })
    console.log(rst);
    // let dictionay = new Dictionay()
    // dictionay.set('hyun', 0831)
    // dictionay.set('lf', 0801)
    // dictionay.set('lz', 0616)
    // console.log(dictionay);
    // let rst_keys = dictionay.keys()
    // console.log(rst_keys);
  </script>
</body>

</html>